package mo.leetcode_top;

public class L329 {

    private int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dfs(matrix, dp, i, j, m, n));
            }
        }
        return res;
    }


    private int dfs(int[][] matrix, int[][] dp, int i, int j, int m, int n) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int max = 1;
        for (int k = 0; k < directions.length; k++) {
            int x = i + directions[k][0];
            int y = j + directions[k][1];
            if (x < 0 || x >=m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) {
                continue;
            }
            int len = dfs(matrix, dp, x, y, m, n) + 1;
            max = Math.max(len, max);
        }
        dp[i][j] = max;
        return max;
    }

}
